import java.util.*;

/**
 * LCR 007. 三数之和
 * https://leetcode.cn/problems/1fGaJU/description/
 */

class Solution3 {
    public int[][] threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<int[]> list = new LinkedList<>();

        for(int i = 0; i < n;) {
            int left = i + 1, right = n - 1, target = -nums[i];
            while(left < right) {
                if(nums[left] + nums[right] > target) {
                    right--;
                } else if(nums[left] + nums[right] < target) {
                    left++;
                } else {
                    list.add(new int[]{i, left, right});
                    left++;
                    right--;
                    // 去重: left, right
                    while(left < right && nums[left] == nums[left - 1]) left++;
                    while(left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重 i
            i++;
            while(i < n && nums[i] == nums[i - 1]) i++;
        }

        int[][] ret = new int[list.size()][3];
        int cur = 0;
        for(int[] x : list) {
            ret[cur][0] = nums[x[0]];
            ret[cur][1] = nums[x[1]];
            ret[cur][2] = nums[x[2]];
            cur++;
        }
        return ret;
    }
}